#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/8/21 20:02
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 中级-岛屿的个数.py
# @Software: PyCharm


class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        rs = len(grid)
        if rs <= 0:
            return 0
        cs = len(grid[0])

        def work(x, y):
            grid[x][y] = '0'
            for s in [(0, -1), (1, 0), (0, 1), (-1, 0)]:
                xx = x + s[0]
                yy = y + s[1]
                if 0 <= xx < rs and 0 <= yy < cs:
                    if grid[xx][yy] == '1':
                        work(xx, yy)
        ans = 0
        for r in range(rs):
            for c in range(cs):
                if grid[r][c] == '1':
                    work(r, c)
                    ans += 1
        return ans


def main():
    solve = Solution()
    grid = [["1", "1", "1", "1", "0"],
            ["1", "1", "0", "1", "0"],
            ["1", "1", "0", "0", "0"],
            ["0", "0", "0", "0", "0"]]
    print(grid)
    print(solve.numIslands(grid))


if __name__ == '__main__':
    main()
